package ljl.codetop300;

import commons.ListNode;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 这不是链表有环，我记错了，这是相交链表
 * 两个一起走，a 走到头了走 b，b 走到头了走 a，相遇的点就是交点
 */
public class _171_list_iner {

  /**
   * 本来想用点简单法，结果发现他妈的不会
   */
  static class test {

    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      if (headA == null || headB == null) return null;
      Set<ListNode> set = new HashSet<>();
      ListNode p = headA;
      while (p != null) {
        set.add(p);
        p = p.next;
      }
      p = headB;
      while (p != null) {
        if (set.contains(p)) return p;
        p = p.next;
      }
      return null;
    }
  }

  /**
   * 再试试
   * 这次蒙对了
   */
  static class test2 {
    /**
     * a 如果是 null，next 就去 b，反之也是一样
     */
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      ListNode pa = headA;
      ListNode pb = headB;
      while (pa != pb) {
        pa = pa == null ? headB : pa.next;
        pb = pb == null ? headA : pb.next;
      }
      return pa;
    }
  }
}
